package 开始的剑指offer8月.二叉树;

import java.util.HashMap;
// https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
// https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/jian-dan-li-jie-di-gui-zhong-jian-er-cha-ursl/
public class 剑指Offer07重建二叉树0830 {

      public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
      }

    class Solution {
        int[] preorder;
        HashMap<Integer, Integer> map = new HashMap<>();
        // 前序遍历 preorder: 根 -- 左 -- 右   第一个肯定是根节点
        // 中序遍历 inorder: 左 -- 根 -- 右
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            this.preorder = preorder;
            for(int i = 0; i < inorder.length; i++){
                map.put(inorder[i], i);
            }
            return rebuild(0, 0, inorder.length - 1);
        }

        // pre_root_index : 根节点 在 前序遍历中的下标
        // in_left_index: 该节点在中序遍历中的左边界
        // in_right_index: 该节点在中序遍历中的右边界
        public TreeNode rebuild(int pre_root_index, int in_left_index, int in_right_index){
            if(in_left_index > in_right_index)  return null;
            // 根节点在中序遍历中的位置：in_root_index
            int in_root_index = map.get(preorder[pre_root_index]);
            // 创建一个根节点
            TreeNode node = new TreeNode(preorder[pre_root_index]);
            // 寻找node的左节点:
            // 在前序遍历中的位置就是  根节点的下标 + 1（右边一个单位）
            // 在中序遍历中的位置就是： 1. 左边界不变，2. 右边界就是根节点的左边一个单位 in_root_index - 1
            node.left = rebuild(pre_root_index + 1, in_left_index, in_root_index - 1);
            // 寻找node的右节点:
            // 在前序遍历中的位置就是  根节点的下标 + 左子树长度 + 1
            // 在中序遍历中的位置就是： 1. 左边界在根节点的右边一个单位  in_root_index + 1, 2. 右边界不变
            node.right = rebuild(pre_root_index + in_root_index - in_left_index + 1, in_root_index + 1, in_right_index);
            return node;
        }
    }

}
